We study the problem of online coloring co-Interval graphs. In this problem, a set of Intervals on the real line is presented to the algorithm, one at a time, and upon receiving each Interval I, the algorithm must assign I a color different from the colors of all previously presented Intervals not intersecting I. The objective is to use as few colors as possible. It is known that the competitive ratio of the simple FIRST-FIT algorithm on the class of co-Interval graphs is at most 2. We show that for the class of unit co-Interval graphs, where all Intervals have equal length, the 2-bound on the competitive ratio of FIRST-FIT is tight. On the other hand, we show that no deterministic online algorithm for coloring unit co-Interval graphs can be better than 3/2-competitive. We then study the effect of randomization on our problem and show a lower bound of 4/3 on the competitive ratio of any randomized algorithm for the unit co-Interval coloring problem. We also prove that for the class of general co-Interval graphs, no randomized algorithm has a competitive ratio better than 3/2.

Please click on PDF to view the abstract.

In general, computation of graph vulnerability parameters is NP-complete. In past, some algorithms were introduced to prove that computation of toughness, scattering number, integrity and weighted integrity parameters of Interval graphs are polynomial. In this paper, two di erent vulnerability parameters of graphs, tenacity and rupture degree are de ned. In general, computing the tenacity of a graph is NP-hard and the rupture degree of a graph is NP-complete, but in this paper, we will show that these parameters can be computed in polynomial time for Interval graphs.

We determine the forbidden induced subgraphs for the intersection of the classes of chordal bipartite graphs and line graphs of acyclic directed graphs. This is a first step towards finding the forbidden induced subgraphs for the class of line graphs of directed graphs.

A set W ,V (G) is called a resolving set, if for every two distinct vertices u,v 2 V (G) there exists w 2 W such that d(u, w) 6= d(v, w), where d(x,y) is the distance between the vertices x and y. A resolving set for G with minimum cardinality is called a metric basis. A graph with a unique metric basis is called a uniquely dimensional graph. In this paper, we establish a family of graph called Solis graph, and we prove that if G is a minimal edge unique base graph with the base of size two, then G belongs to the Solis graphs family. Finally, an algorithm is given for , nding the metric dimension of a Solis graph.

The Hosoya index $Z(G)$ of a graph $G$ is the total number of matchings in it. In this paper, the recursive formulas of the Hosoya index of semitotal graph $Q(G)$ and total graph $T(G)$ for certain graphs $G$ are obtained. Moreover, we obtain the bounds of the Hosoya index of semitotal and total graphs of a connected graph $G$.

Let $t_p(G)$ denote the number of paths in a graph $G$ and let $f:E\rightarrow \mathbb{Z}^+$ be an edge labeling of $G$. The weight of a path $P$ is the sum of the labels assigned to the edges of $P$. If the set of weights of the paths in $G$ is $\{1,2,3,\dots,t_p(G)\}$, then $f$ is called a Leech labeling of $G$ and a graph which admits a Leech labeling is called a Leech graph. In this paper, we prove that the complete bipartite graphs $K_{2,n}$ and $K_{3,n}$ are not Leech graphs and determine the maximum possible value that can be given to an edge in the Leech labeling of a cycle.

A coalition in a graph G = (V, E) consists of two disjoint sets V1 and V2 of vertices, such that neither V1 nor V2 is a dominating set, but the union V1 , V2 is a dominating set of G. A coalition partition in a graph G of order n = |V| is a vertex partition π,= {V1, V2, …, , Vk} such that every set Vi either is a dominating set consisting of a single vertex of degree n-1, or is not a dominating set but forms a coalition with another set Vj. Associated with every coalition partition π,of a graph G is a graph called the coalition graph of G with respect to π, , denoted CG(G,π, ), the vertices of which correspond one-to-one with the sets V1,V2,…, , Vk of π,and two vertices are adjacent in CG(G,π,) if and only if their corresponding sets in π,form a coalition. In this paper, we initiate the study of coalition graphs and we show that every graph is a coalition graph.